Error correction codes are often employed in communication systems to provide increased resilience to channel noise. Generally, error correction encoding techniques typically employ convolutional, block or concatenated coding of the data before the signal is modulated so that errors introduced by noise and interference on the channel may be corrected. One popular family of linear low rate error correction codes having large minimum distances is first order Reed-Muller codes. Many other codes of higher rates can be considered as unions of cosets of first order Reed-Muller codes. These codes can also be used in concatenation with other codes. For a discussion of Reed-Muller codes see, for example, Y. Be'ery and J. Snyders, “Optimal Soft Decision Block Decoders Based On Fast Hadamard Transform,” IEEE Trans. on Inf. Theory, v. IT-32, 355-364 (1986); or R. R. Green, “A Serial Orthogonal Decoder,” JPL Space Programs Summary, v. 37-39-IV, 247-253 (1966), each incorporated by reference herein.
The received signal, which is typically corrupted by the noise and interference on the channel, must be decoded at the receiver. Typically, maximum a posteriori (MAP) decoding techniques are applied to decode signals encoded using error correction codes to make maximum probability decisions about each transmitted bit. For a detailed discussion of conventional decoding techniques for Reed-Muller codes see, for example, A. Ashikhmin and S. Litsyn, “Fast Decoding of First Order Reed-Muller and Related Codes,” Designs, Codes and Cryptography, vol. 7, pp. 187-215, 1996.
One particular implementation of the MAP decoding algorithm, commonly referred to as the BCJR algorithm, was proposed in L. R. Bahl, J. Cocke, F. Jelinek and J. Raviv, “Optimal Decoding of Linear Codes for Minimizing Symbol Error Rate”, IEEE Trans. Inform. Theory, V. IT-20, 284-287 (March, 1974), incorporated by reference herein. The BCJR algorithm is a symbol-by-symbol decoder based on a trellis representation of a code. The BCJR algorithm for binary first order Reed-Muller codes has a complexity that is proportional to n2, where n is the code length.
A need exists for a MAP decoding technique having reduced complexity. A further need exists for a MAP decoding technique that permits faster decoding by permitting a parallel implementation.